# class Solution:
#     def isValidSerialization(self, preorder: str) -> bool:
#         nodes = preorder.split(',')
#         slots = 1  # 初始有一个槽位（根）
#
#         for node in nodes:
#             slots -= 1  # 每个节点占一个槽位
#             if slots < 0:
#                 return False
#             if node != '#':
#                 slots += 2  # 非空节点提供两个新槽位
#
#         return slots == 0


class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        stack = []

        for node in nodes:
            stack.append(node)

            # 当栈顶是两个 #，且倒数第三个是非 #，说明可以归约为一个 #
            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':
                # 弹出两个 #
                stack.pop()
                stack.pop()
                # 弹出父节点
                stack.pop()
                # 压入一个 #
                stack.append('#')

        # 最终只剩一个 #
        return len(stack) == 1 and stack[0] == '#'


if __name__ == '__main__':
    s = Solution()
    preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
    serialization = s.isValidSerialization(preorder)
    print(serialization)
